<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>桶排序</title>
  </head>
  <body>
    <script>
      // arr数组，size是每个桶的数组长度：原则就是把数组分成多个小数组[[2,1,2],[5,3,4],[7,8,9]],然后再针对每个小数组排序之后再合并
      function bucketSort(arr, size) {
        if (arr.length < 2) {
          return arr;
        }
        let buckets = createBukets(arr, size);
        let bukets = buckets.map((item) => {
          item.sort((a, b) => a - b);
          return item;
        });
        let result = [];
        bukets.map((item) => {
          result.push(...item);
        });

        return result;
      }
      //   创建桶
      function createBukets(arr, size) {
        let min = Math.min(...arr);
        let max = Math.max(...arr);

        let buketsCount = Math.floor((max - min) / size) + 1;
        let bukets = [];
        for (let i = 0; i < buketsCount; i++) {
          bukets[i] = [];
        }
        for (let j = 0; j < arr.length; j++) {
          let index = Math.floor((arr[j] - min) / size); //计算当前数字应该属于哪个桶
          bukets[index].push(arr[j]);
        }

        return bukets;
      }

      console.log(bucketSort([9, 8, 7, 6, 5, 4, 3, 2, 1, 44], 3));
    </script>
  </body>
</html>
